// 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
// 输入: s = "leetcode", wordDict = `["leet", "code"]`
// 输出: true
// 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

// 思路1， 回溯
function wordBreak(s, wordDict) {
    let memory = {}
    function backtracking(startIndex) {
        if (startIndex >= s.length) {
            return true
        }
        if (memory[startIndex] === false) {
            return false
        }
        for (let i = startIndex; i < s.length; i++) {
            let word = s.substring(startIndex, i + 1)
            if (wordDict.includes(word) && backtracking(i + 1)) {
                return true
            }         
        }
        memory[startIndex] = false
        return false
    }
    return backtracking(0)
}


// 思路2， 动态规划
// 单词就是物品，字符串就是背包，完全背包问题
// 1. `dp[i]`，字符串长度为i，表示可以被拆分为一个或多个在字典中出现的单词
// 2. 递推公式`dp[i] = wordDict.includes(s.substring(j, i) && dp[j])`
// 3. `dp[0] = true`，累计的基础，必须为true
// 4. 遍历顺序，这个题的字符串相当于背包，其顺序是不能变的，必须从前往后，所以外层是背包，内层是物品，正序遍历
// 5. 举例推导

function wordBreak(s, wordDict) {
    let dp = new Array(s.length + 1).fill(false)
    dp[0] = true
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            // 必须这么判断
            if (dp[j] && wordDict.includes(s.substring(j, i))) {
                dp[i] = true
            }
        }        
    }
    return dp[s.length]
}

// 思路3，动态规划
function wordBreak(s, wordDict) {
    let dp = new Array(s.length + 1).fill(false)
    dp[0] = true
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < wordDict.length; j++) {
            let word = wordDict[j]
            if (i >= word.length) {
                if (dp[i - word.length] && s.substring(i - word.length, i) === word) {
                    dp[i] = true
                }
            }            
        }
    }
    return dp[s.length]
}

let s = "applepenapple", wordDict = ["apple", "pen"]
console.log(wordBreak(s, wordDict))